package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 * 深度优先搜索, 自顶到底的搜索, 到最后的叶子节点才add到list
 *
 * @author fy
 * @date 2022-04-23 20:26
 */
public class Solution257_2 {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        concatPath(root, "", res);
        return res;
    }

    private void concatPath(TreeNode node, String path, List<String> paths) {
        if (node == null) {
            return;
        }
        StringBuilder sb = new StringBuilder(path).append(node.val);
        if (node.left == null && node.right == null) {
            // 到最后到叶子节点时加入
            paths.add(sb.toString());
            return;
        }
        sb.append("->");
        String newPath = sb.toString();
        concatPath(node.left, newPath, paths);
        concatPath(node.right, newPath, paths);
    }

}
